导读
分解300位和5000位的数字，量子算法会把所需时间从15万年减到不足1秒钟，从50亿年减到2分钟！
西瓜视频：
https://www.ixigua.com/6902292563307266573
本视频发布于2020年12月4日，播放量已超百万
前三次我们说到，中央集体学习的量子科技，主要指的是量子信息（让中央集体学习的量子科技究竟是啥？这个科普我已经做了五年（一）量子是什么 | 袁岚峰）。它分为量子通信和量子计算两大领域，正如我们平时用的手机属于通信，计算机属于计算。这次我们就来讲解量子计算。
你可能早已听说过，量子计算是真正的颠覆性技术，能够做到很多现有的计算机做不到的事。但是，量子计算为什么这么厉害呢？很奇妙，大多数人的理解都是错误的。
媒体常见的说法是：量子计算机的运算速度特别快，比经典计算机快得多。这听起来很容易理解，就好像486比386快，386比286快。如果媒体想解释原理，还会说这是因为量子计算机是并行计算，一次能处理很多任务，而经典计算机一次只能处理一个任务。
然而，这种话只能蒙住外行。如果你对计算机科学稍有了解，你立刻就知道，并行计算并不是什么特别的东西，现在的计算机就经常在用。例如所有的超级计算机，神威太湖之光、天河二号等等，都是用大规模并行计算达到超高速度的（中国超算全自主，重夺第一已出发 | 袁岚峰）。
所以，量子计算真正的原理是什么？我来向大家解读一下。这里的关键在于，量子计算机不是干什么都特别快，而是只对某些问题特别快，因为对这些问题能设计出快速的量子算法。也就是说，量子计算机优于经典计算机，并不是像486优于386那样干什么都强，而是好比你的计算机能运行某个游戏，而别人的计算机不能运行这个游戏，所以在这方面你的计算机强。最基本的道理是，经典计算机的基本操作单元是比特，而量子计算机的基本操作单元是量子比特。比特好比开关，只有开和关两个状态。而量子比特好比旋钮，有无穷多个状态。所以显然，量子比特有可能做到比经典比特更多的事。如果有n个经典比特，每一个有两个状态，它们的组合就总共有2n个状态。如果想知道一个操作对n个比特产生的效果，就需要把这个操作作用到这2n个状态上，把所有的结果都试一遍。也就是说，需要2n次操作。2n是个增长非常快的函数。学过数学的人都知道，指数增长比任何的多项式增长都要快，比如说比n10000都快。所以随着n的增长，经典计算机的计算量很快就会爆炸。
c(000…) |000…> + c(100…) |100…> + c(010…) |010…> + … + c(111…) |111…>，其中每一个c都是一个系数，总共有2n个这样的系数。现在重点来了：对这样一个一般的状态做一次操作，就可以同时改变2n个系数，相当于对n个比特的经典计算机进行了2n次操作。一个顶2n个！这是一个吓死人的优势。所谓量子计算机的优势来自并行计算，实际指的就是这个意思。如果使用得当，这可以带来指数级的加速。原来需要上亿年的任务，现在可能一秒钟就能搞定，这是多么惊人的进步！但是且慢，这一切有个前提，“如果使用得当”。什么意思呢？因为把数据读出来是大问题。因此，量子计算确实具有巨大的优势，但这是个潜在的优势，需要非常巧妙的算法才能发挥出来。只对少数特定的问题，人们设计出了这样的算法。而对于大多数的问题，量子计算还没有表现出任何优势。你也许会感到很失望，原来量子计算没什么用啊？别急。目前已知的能发挥量子计算优势的问题虽然不多，但其中有些就非常重要，例如因数分解（factorization）和无结构数据库的搜索。下面，我们就来解释一下量子因数分解。因数分解是什么？就是把一个合数分解成质因数的乘积，例如21 = 3 × 7。只需要小学数学水平，就能理解这个概念。但重点在于，因数分解是一个经典的数学难题。你也许会感到很奇怪，这有什么难的？呐，分解一个小的数字当然很容易，你不管三七二十一就能分解21。但是来分解下面这个数看看：267 - 1 = 147, 573, 952, 589, 676, 412, 927。这是一个21位数。它是质数还是合数呢？这就远不是一眼能看出来的了。1644年，也就是李自成进北京、明朝灭亡的那一年，法国数学家梅森（Marin Mersenne，1588 - 1648）提出这个数是一个质数。
在那之后的很长时间里，人们都这么认为。直到1903年，清朝都快亡了，人们才发现它其实是一个合数，等于193, 707, 721 × 761, 838, 257, 287。
因数分解为什么这么困难呢？因为没有特别高效的算法。如果让我们分解一个数字N，我们能够想到的最简单的算法，就是从2开始一个个往上试。先问：它能不能被2分解？如果不能，再问：它能不能被3分解？这样一个个试，直到根号N为止。如果到根号N都分解不了，说明它是个质数。由此可见，尝试的次数大约是根号N。这是个特别简单也特别愚笨的算法。如果N表示成二进制有n位数，也就是N约等于2n，那么计算量就约等于根号N即2n/2。这正是指数增长，所以随着位数的增长，计算量很快就爆炸了。显然，数学家不会满足于这么愚笨的算法。经过几百年的研究，人们提出了很多改进的算法，目前最高效的算法叫做“数域筛”（number field sieve）。这些算法确实快了很多，然而在基本面上没有变化，计算量仍然是指数增长的。比如说，一台计算机每秒做一万亿次运算，它用数域筛算法分解一个300位的数字需要15万年，分解一个5000位的数字需要……50亿年！地球的年龄也不过是46亿年而已！所以，因数分解仍然是一个难题。奇妙的是，分解不开对我们是一件好事，——可以用来保密。当今世界最常用的密码体系之一叫做RSA，它就是基于因数分解的困难性设计出来的。RSA这个名字，是三位发明者李维斯特（Ron Rivest）、萨莫尔（Adi Shamir）和阿德曼（Leonard Adleman）的姓氏首字母缩写。
大致而言，RSA的操作方式是这样的。让我们把信息的发送方叫做Alice，接收方叫做Bob。首先，Bob取两个很大的质数p和q，求出它们的乘积这一步是很容易的。但是如果有人只知道N，想求出p和q，就是很困难的。然后，Bob把N向全世界公布，这叫做公钥。把p和q藏好不公布，这叫做私钥。注释一下，密码学里的密钥这个词念mì yuè。钥匙的钥（yào）这个字是个多音字，在这里念yuè。你去百度一下或者翻一下字典，就能找到这个答案。
然后，Alice把想发送的信息用公钥N加密，用公开信道发给Bob。Bob拿到密文，用自己的私钥p和q就可以解密。其他人虽然拿到了密文，但分解不开N，算不出p和q，所以无法窃密。
这确实是一个非常巧妙的思想。在这个意义上，我们平时的网购、网上银行、浏览网站等习以为常的做法，都是依靠因数分解的困难性保驾护航的。经常有无知的人说，学数学有什么用，又不能用来买菜。但实际上，如果没有数学，你买菜的时候钱早就被别人转走了！然而，RSA真的可靠吗？这其实并没有证明，只是个经验而已。永远不能排除这种可能：将来有个聪明人发明一种高效的算法，一下子就解决了因数分解。甚至还有可能，这样的算法已经发明出来了，只不过没有公布。设想一下，如果你是美国情报部门的领导人，你的手下有人发明了破解RSA的算法，你会公布吗？显然，你更可能采取的做法是闷声发大财，在暗中破解别人自以为安全的密码。
如果说这些担心是“隐患”，那么量子计算已经带来了一个“明患”。前面谈的因数分解算法都是经典计算机上的算法，其中最高效的是数域筛。但是在1994年，美国科学家肖尔（Peter Shor）提出了一种高效的量子因数分解算法。
彼得·肖尔（http://www-math.mit.edu/~shor/）
高效到什么程度呢？分解一个n位数的计算量大约是n2。跟以前的指数增长相比，这是一个指数级的节约。举个例子，同样还是分解300位和5000位的数字，量子算法会把所需时间从15万年减到不足1秒钟，从50亿年减到2分钟！许多媒体说，量子计算机可以破解全世界所有的密码。这话基本是可以成立的，很有可能现在的各种密码都会被量子计算破解。不过要加个限制条件，——除了量子密码之外。只有魔法才能打败魔法，只有量子才能打败量子。量子密码保密的基础是物理原理，而不是数学，所以即使是量子计算也无法破解。关于量子密码，我们会在后面介绍。话说回来，量子计算只是在算法层面破解了RSA。而在硬件层面，量子计算机还远没有达到实用的程度。迄今为止，量子分解的最大的数是这是科大的杜江峰和彭新华等人在2017年实现的，他们在算法上又做了不少改进（https://arxiv.org/abs/1706.08061）。
杜江峰和彭新华等人2017年用量子算法分解291311的论文（https://arxiv.org/abs/1706.08061）
这离破解RSA有多远呢？目前常用的RSA密钥长度是1024，也就是说，密钥是二进制的1024位数。上面提到的291, 311是一个十进制的六位数，换算成二进制是一个19位数，离1024位还远。因此，我们现在还在用RSA。但数据安全工作者都知道，这种状况不会持续太久了。
谷歌首席执行官预测，加密技术的终结可能在5年内到来那么，量子计算什么时候能实用呢？下次，我们就来介绍这方面的进展。
背景简介：本文作者袁岚峰，中国科学技术大学化学博士，中国科学技术大学合肥微尺度物质科学国家研究中心副研究员，科技与战略风云学会会长，“科技袁人”节目主讲人，安徽省科学技术协会常务委员，中国青少年新媒体协会常务理事，入选“典赞·2018科普中国”十大科学传播人物，微博@中科大胡不归，知乎@袁岚峰（https://www.zhihu.com/people/yuan-lan-feng-8）。